/**
 * @file   main.cpp
 * @author  谢飞扬
 * @date   Sat Oct 15 11:24:33 2022
 * 
 * @brief  二叉搜索树排序数组，测试顺序插入时的最坏效率，及随机打乱数组的平均排序效率
 * 
 * @version Copyright (c) 2022,浙江大学-信息与计算科学2101.
 * 
 */

#include <iostream>
#include "BinarySearchTree.h"
#include<vector>
#include<ctime>
#include<cstdlib>
using namespace std;

/** 
 * 二叉搜索树排序
 * 
 * @param _arr 数组，排序后元素从小到大
 * @param _mode 数组模式
 */
template <typename Comparable>
void BSTSorting(vector<Comparable> & _arr, int _mode = 0)
{
    /// 随机数种子，用于生成真正的随机数
    srand((unsigned int)time(nullptr));
    /// 如果_mode输入不是0或1,抛出错误
    if(_mode!=0 && _mode!=1)
    {
	throw IllegalArgumentException{};
    }
    /// _mode=1时打乱数组，若为0则不做处理
    if(_mode==1)
    {
	/**
	 * 打乱数组采用洗牌算法
	 * 逐一打乱数组元素
	 */
        for(int i=_arr.size()-1;i>0;i--)
        {
	    /// index随机下标，用于随机访问数组元素
 	    int index = (int)(rand()%i);
 	    Comparable temp = _arr[index];
 	    _arr[index]=_arr[i];
	    _arr[i]=temp;
        }
    }
    /// clock_t ctime库下的类类型，用于程序计时
    clock_t start,end;
    /// 计时开始
    start=clock();
    BinarySearchTree<Comparable> t;
    /// 用迭代器遍历数组，调用BinarySearchTree成员函数insert自动完成排序
    for(typename vector<Comparable>::iterator itr=_arr.begin();itr!=_arr.end();++itr)
    {
	t.insert(*itr);
    }
    /// 返回排好序的数组
    _arr=t.outarray();
    /// 计时结束
    end=clock();
    cout<<"the sorting spent "<<(double)(end-start)/CLOCKS_PER_SEC<<" s"<<endl;
    return;
}

/** 
 * 主函数测试程序
 * 
 * @return 
 */
int main(int argc,char*argv[])
{
    vector<int> arr;
    for(int i=0;i<100000;++i)
    {
	arr.push_back(i);
    }
    cout<<"顺序插入"<<endl;
    BSTSorting(arr);
    cout<<"乱序插入"<<endl;
    BSTSorting(arr,1);
    return 0;
}
